package leetcode.editor.cn;
//给你一个整数数组 nums，请你将该数组升序排列。 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 
//输入：nums = [5,2,3,1]
//输出：[1,2,3,5]
// 
//
// 示例 2： 
//
// 
//输入：nums = [5,1,1,2,0,0]
//输出：[0,0,1,1,2,5]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 5 * 104 
// -5 * 104 <= nums[i] <= 5 * 104 
// 
// Related Topics 数组 分治 桶排序 计数排序 基数排序 排序 堆（优先队列） 归并排序 
// 👍 826 👎 0


import java.util.Random;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution87 {

    private int[] temp;

    public int[] sortArray(int[] nums) {
        // 为了避免出现耗时的极端情况，先随机打乱
        shuffle(nums);
        temp = new int[nums.length];
        sort(nums, 0, nums.length - 1);
        return nums;
    }

    // 洗牌算法，将输入的数组随机打乱
    private  void shuffle(int[] nums) {
        Random rand = new Random();
        int n = nums.length;
        for (int i = 0 ; i < n; i++) {
            // 生成 [i, n - 1] 的随机数
            int r = i + rand.nextInt(n - i);
            swap(nums, i, r);
        }
    }

    // 原地交换数组中的两个元素
    private  void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /**
     * 归并
     * @param nums
     * @param low
     * @param high
     */
    private void sort(int[] nums, int low, int high) {
        if (low >= high) {
            return;
        }
        int mid = low + (high - low) / 2;
        sort(nums, low, mid);
        sort(nums, mid + 1, high);
        merge(nums, low, mid, high);
    }

    private void merge(int[] nums, int low, int mid, int high) {
        System.arraycopy(nums, low, temp, low, high - low + 1);
        if (temp[mid] > temp[mid + 1]) {
            int l = low;
            int m = mid + 1;

            for (int p = low; p <= high; p++) {
                if (l == mid + 1) {
                    // 左半边数组已全部被合并
                    nums[p] = temp[m++];
                } else if (m == high + 1) {
                    // 右半边数组已全部被合并
                    nums[p] = temp[l++];
                } else if (temp[l] > temp[m]) {
                    nums[p] = temp[m++];
                } else if (temp[l] <= temp[m]) {
                    nums[p] = temp[l++];
                }
            }
        }
    }

    /**
     * 快排
     * @param nums
     * @param low
     * @param high
     */
    private void sort1(int[] nums, int low, int high) {
        if (low >= high) {
            return;
        }
        // 对 nums[lo..hi] 进行切分
        // 使得 nums[lo..p-1] <= nums[p] < nums[p+1..hi]
        int p = partition(nums, low, high);
        // 去左右子数组进行切分
        sort1(nums, low, p - 1);
        sort1(nums, p + 1, high);
    }

    private int partition(int[] nums, int low, int high) {
        int matchIndex = low;
        int match = nums[matchIndex];

        while (low <= high) {
            if (match < nums[low]) {
                int temp = nums[low];
                nums[low] = nums[high];
                nums[high] = temp;
                high--;
            } else {
                low++;
            }
        }
        nums[matchIndex] = nums[low-1];
        nums[low-1] = match;
        return low-1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
